package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-30 09:32
 **/
public class LeetCode509 {

    /*int[] nums;

    public int fib(int n) {
        init(n);
        if (n < 2) {
            return n;
        }
        if (nums[n - 1] == 0) {
            nums[n - 1] = fib(n - 1);
        }
        if (nums[n - 2] == 0) {
            nums[n - 2] = fib(n - 2);
        }
        return nums[n - 1] + nums[n - 2];
    }

    private void init(int n) {
        if (nums == null) {
            nums = new int[n + 1];
        }
    }*/

    /*public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0;
        int q = 0;
        int r = 1;
        for (int i = 1; i < n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }*/

    public int fib(int n) {
        if (n == 0) {
            return 1;
        }
        int[][] a = {{1,1}, {1,0}};
        return pow(a, n - 1);
    }

    private static int pow(int[][] a, int n) {
        int[][] res = {{1,0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                res = multiply(res, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return res[0][0];
    }

    private static int[][] multiply(int[][] a, int[][] b) {
        int[][] res = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int i1 = 0; i1 < 2; i1++) {
                res[i][i1] = a[i][0] * b[0][i1] + a[i][1] * b[1][i1];
            }
        }
        return res;
    }
}
